package com.fzkj.algorithm;

public class NumOfLand { //中等
    /**
     * 给你一个由 '1'（陆地）和 '0'（水）组成的的二维网格，请你计算网格中岛屿的数量。
     * 岛屿总是被水包围，并且每座岛屿只能由水平方向或竖直方向上相邻的陆地连接形成。
     * 此外，你可以假设该网格的四条边均被水包围。
     * 示例 1:
     * 输入:
     * 11110
     * 11010
     * 11000
     * 00000
     * 输出: 1
     *
     * 示例 2:
     * 输入:
     * 11000
     * 11000
     * 00100
     * 00011
     * 输出: 3
     * 解释: 每座岛屿只能由水平或竖直方向上相邻的陆地连接而成。
     */
    public int numIslands(char[][] grid) {
        // 递归
        int result = 0;
        if (grid.length==0 || grid[0].length == 0) return 0;
        int hang = grid.length;
        int lie = grid[0].length;
            for (int i = 0; i < hang; i++){
                for(int j = 0; j < lie; j++){
                    if (grid[i][j]=='0') continue;
                    // 不等于 0 就调用dfs方法，找到相邻的1，变成0
                    dfs(grid,i,j); // 递归
                    result++;
                }
            }
        return result;
    }

    // 找到当前元素的四邻域中的陆地 ‘1’ 并制成 ‘0’
    private void dfs(char[][] grid, int i, int j) {
        if (i<0 || j<0 || i+1>grid.length || j+1>grid[0].length) return;
        if (grid[i][j]=='0')return;
        grid[i][j] = '0'; //把当前的置为 0
        dfs(grid,i-1,j);
        dfs(grid,i+1,j);
        dfs(grid,i,j-1);
        dfs(grid,i,j+1);
    }

    public static void main(String[] args) {
        NumOfLand num = new NumOfLand();
        int result = num.numIslands(new char[][]{
                {'1','1','1','1','0'},
                {'1','1','0','1','0'},
                {'1','1','0','0','0'},
                {'0','0','0','0','1'}
        });
        System.out.println(result);
    }
}